﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BinarySearch
{
	/// <summary>
	/// 折半无序（用快排活堆排）的时间复杂度：O(NlogN)+O(logN);
	/// 折半有序的时间复杂度：O(logN);
	/// </summary>
	class Program
	{
		static void Main(string[] args)
		{
			List<int> list = new List<int>() { 3, 7, 9, 10, 11, 24, 45, 66, 77 };
			var result = BinarySearch(list, 45);
			if (result != -1)
				Console.WriteLine("45 已经在数组中找到，索引位置为：" + result);
			else
				Console.WriteLine("没有找到！");
			Console.Read();
		}

		public static int BinarySearch(List<int> list, int key)
		{
			//最低线
			int low = 0;
			//最高线
			int high = list.Count - 1;
			while (low < high)
			{
				var middle = (low + high) / 2;
				if (list[middle] == key)
				{
					return middle;
				}
				else
				{
					if (list[middle] > key)
					{
						//下降一半
						high = middle - 1;
					}
					else
					{
						//上升一半
						low = middle + 1;
					}
				}
			}
			//未找到
			return -1;
		}
	}
}
